package top.humbleyuan.divide_conquer;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 18:41
 * @Des 寻找重复数
 */
public class LeetCode_287 {
    public static void main(String[] args) {
        int[] nums = {1,6,2,3,5,6,4};

        int same = findSame(nums, 1, nums.length);
        System.out.println(same);
    }

    public static int findSame(int[] nums, int begin, int end) {
        if(begin == end) {
            return begin;
        }

        int mid = (begin + end) >> 1;

        // 这里注意取base，得到>= base的数count是否> mid
        // 这里不能写成(mid - 1, mid + 1)的二分，应为mid也有可能是
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] <= mid) {
                count++;
            }
        }

        if(count > mid) {
            end = mid;
        } else {
            begin = mid + 1;
        }

        return findSame(nums, begin, end);
    }
}
